package com.aug_leo.datastructure.linkedlist;

/**
 * 删除倒数节点
 */
public class E03Leetcode19 {

    /*
    recursion(ListNode p=1, int n=2) {
        recursion(ListNode p=2, int n=2) {
            recursion(ListNode p=3, int n=2) {
                recursion(ListNode p=4, int n=2) {
                    recursion(ListNode p=5, int n=2) {
                        recursion(ListNode p=null, int n=2) {
                            return 0;
                        }
                        return 1;
                    }
                    return 2;
                }
                if(返回值 == n == 2) {
                    删除
                }
                return 3;
            }
            return 4;
        }
        return 5;
    }
    */


    /**
     * <h3>方法一 递归</h3>
     * 从链表末尾移除第n个几点
     *
     * @param head 链表头节点
     * @param n    要移除的节点的位置（从末尾开始计数）
     * @return 移除节点后的链表头节点
     */
    public ListNode removeNthFromEnd1(ListNode head, int n) {
        // 创建一个哨兵节点，简化边界条件处理
        ListNode sentinel = new ListNode(-1, head);
        // 若删除的是第一个节点，它没有上一个节点，因此可以加一个哨兵来解决
        // 从哨兵节点开始递归
        recursion(sentinel, n);
        // 返回更新后的链表头节点
        return sentinel.next;
    }

    /**
     * 递归函数，用于计算链表中指定节点的倒数位置
     *
     * @param pointer 当前遍历的链表节点
     * @param n       链表的长度
     * @return 当前节点的倒数位置
     */
    private int recursion(ListNode pointer, int n) {
        // 当指针遍历到链表末尾时，返回0
        if (pointer == null) {
            return 0;
        }

        // 递归调用，计算下一个节点的倒数位置
        int nth = recursion(pointer.next, n); // 下一个节点的倒数位置
        System.out.println(pointer.val + " " + nth);
        // 如果下一个节点的倒数位置的倒数位置是n，则删除下一个节点
        if (nth == n) {
            pointer.next = pointer.next.next;
        }
        // 返回当前节点的倒数位置，即下一个节点的倒数位置 + 1
        return nth + 1;
    }

    /*
        n=2
        p1
        p2
        s -> 1 -> 2 -> 3 -> 4 -> 5 -> null

             p2
        s -> 1 -> 2 -> 3 -> 4 -> 5 -> null

                  p2
        s -> 1 -> 2 -> 3 -> 4 -> 5 -> null

        p1             p2
        s -> 1 -> 2 -> 3 -> 4 -> 5 -> null

                       p1             p2
        s -> 1 -> 2 -> 3 -> 4 -> 5 -> null
     */

    /**
     * <h3>方法二 快慢指针</h3>
     * 从链表末尾移除第n个几点
     *
     * @param head 链表头节点
     * @param n    要移除的节点的位置（从末尾开始计数）
     * @return 移除节点后的链表头节点
     */
    public ListNode removeNthFromEnd2(ListNode head, int n) {
        // 创建一个哨兵节点，简化链表操作
        ListNode sentinel = new ListNode(-1, head);
        // 初始化两个指针，都指向哨兵节点
        ListNode pointer1 = sentinel;
        ListNode pointer2 = sentinel;
        // 将pointer2指针向前移动n+1个位置，使其与pointer1指针之间有n个节点的距离
        for (int i = 0; i < n + 1; i++) {
            pointer2 = pointer2.next;
        }
        // 移动pointer1和pointer2指针，直到pointer2指针到达链表末尾
        // 此时pointer1指针位于待删除节点的前一个节点位置
        while (pointer2 != null) {
            pointer1 = pointer1.next;
            pointer2 = pointer2.next;
        }
        // 删除pointer1指针的下一个节点
        pointer1.next = pointer1.next.next;
        // 返回链表的头节点
        return sentinel.next;
    }

    public static void main(String[] args) {
        ListNode head = ListNode.of(1, 2, 3, 4, 5);
//        ListNode head = ListNode.of(1,2);
        System.out.println(head);
        System.out.println(new E03Leetcode19()
                .removeNthFromEnd2(head, 5));


    }

}
